#!/usr/bin/env python
# -*- coding: utf-8 -*-
# 
# Copyright (c) 2017 Baidu.com, Inc. All Rights Reserved
# 

"""
File: run19.py
Author: zhangyang(zhangyang40@baidu.com)
Date: 2018/1/5 0005 15:13
"""
"""
题目描述
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。
假设输入的数组的任意两个数字都互不相同。
"""


class Solution:
    def VerifySquenceOfBST(self, sequence):
        length = len(sequence)
        if length == 0:
            return False
        if length == 1:
            return True
        root = sequence[-1]
        left = 0
        while sequence[left] < root:
            left += 1
        for j in range(left, length - 1):
            if sequence[j] < root:
                return False
        return self.VerifySquenceOfBST(sequence[:left]) or self.VerifySquenceOfBST(sequence[left:length - 1])

    """
    
            size = len(sequence) - 1
        if 0 == size: return False;
        i = 0
        while size != 0:
            while sequence[i] < sequence[size]:
                i += 1
            while sequence[i] > sequence[size]:
                i += 1
            if i < size: return False
            i = 0
            size -= 1
        return True
    """
